\documentclass[fleqn,10pt]{article}
\usepackage{graphicx} % Required for inserting images
\usepackage{xeCJK} 
\usepackage{amsmath}
\usepackage{pgfplots}
\usepackage{subcaption}
\usepackage{listings}
\usepackage{mdframed}

\title{Homework03  Report  of  D.S.A.\\{Four-rule Hybrid Calculator}}
\author{3220101611  Han Yaoting}
\date{\today}

\begin{document}
\flushbottom
\maketitle
\tableofcontents


\section {Introduction}
This is a $C^{++}$ project, for the expression entered by the user, 
it can ignore the illegal characters in it and judge whether the expression is legal or not, 
and realizes a four-rule mixed operation expression conversion and evaluation function.

    \noindent The whole project consists of $main.cpp$, $makefile$, $run$, $Doxyfile$, $report.tex$, $input.txt$.

\section{Project Analysis}
    \subsection{$main.cpp$}
    The main part of the project carries the functions of judging the legitimacy of expressions, 
    transforming and computing.
    \noindent Here's an analysis of the functions and code flows.  
        \subsubsection{Functions}
            \begin{itemize}
                \item $report\_Error(\;)$:\; Used to output an error message and end the program in case of an invalid expression;
                \item $report_Error_zero(\;)$:\; Used to output an error message and end the program in case of a zero divisor;
                \item $Precedence(char\;op)$:\; Used to prioritize operators. $+$ and $-$ have a priority of $1$, $*$ and $/$ have a priority of $2$, 
                and other operators have a priority of $0$;
                \item $calculate(double\;num\_1, double\;num\_2, string\;op)$:\; Used to calculate the result of an operation with two numbers. 
                Depending on the operator ($op$), the corresponding addition, subtraction, multiplication, and division operations are performed, 
                and the result is returned;
                \item $remove\_Invalid\_Chars(const\;std::string\& \;input)$:\; Used to remove invalid characters from the input string, 
                leaving only numbers, operators, parentheses, and spaces. Copy valid characters into a new string by iterating through the input string;
                \item $Infix\_To\_Postfix(const\;std::string\& \;infix)$:\; Used to convert an infix expression to a suffix expression. 
                By traversing the characters of the infix expression, the corresponding processing is carried out according to the type of the current character: 
                in the case of numeric characters, they are added to the temporary numeric string; If it's a decimal point character, 
                check its legitimacy and add it to the temporary numeric string; If it is an operator character, the temporary numeric string is queued to the suffix expression, 
                and then the operator is added to the operator stack and the relevant flag bits are updated; In the case of an opening bracket character, 
                a temporary numeric string is added to the suffix expression queue, and the opening bracket character is added to the operator stack, 
                and the associated flag bits are updated; In the case of the closing bracket character, the temporary numeric string is queued for the suffix expression, 
                and then the operators in the operator stack are ejected and queued for the suffix expression until the opening bracket character is encountered, 
                and then the opening bracket character is ejected from the operator stack. Finally, check whether the number of left and right brackets matches, 
                if they do not match or there are other illegal cases, the $report\_Error(\;)$ function is called and an error is reported;
                \item $calculate\_Postfix(const\;std::queue<string>\& \;postfix)$:\; Used to calculate the value of the suffix expression. 
                By taking the string from the queue of suffix expressions, each element is processed: if it is a numeric string, 
                it is converted to a double type and pressed into the number stack; If it is an operator string, 
                two operands are ejected from the stack of numbers for the corresponding operation, and the result is pressed into the stack. Finally, 
                determine whether there is only one element in the number stack, and call the $report\_Error(\;)$ function to report an error if not;
                \item $main(\;)$:\; This function is the main entry function of the program. First, get the infix expression string entered by the user, 
                and then call the $remove\_Invalid_Chars(\;)$ function to remove the invalid characters and get the processed infix expression string. 
                Next, the $Infix\_To\_Postfix(\;)$ function is called to convert the infix expression to a suffix expression and return the suffix expression queue. 
                Finally, the $calculate\_Postfix(\;)$ function is called to calculate the value of the suffix expression and output the result.
            \end{itemize}
        \subsubsection{Codes}
            \begin{mdframed}[linewidth=0.5pt,linecolor=black]
            \begin{lstlisting}[language=C++, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

void report_Error(){
    std::cout << "Error. The expression is illegal." << std::endl;
    exit(0);
}

void report_Error_zero(){
    std::cout << "Error. One of the divisors in the expression is 0." << std::endl;
    exit(0);
}

int Precedence(char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

double calculate(double num_1, double num_2, string op) {
    if (op == "+") return num_1 + num_2;
    if (op == "-") return num_1 - num_2;
    if (op == "*") return num_1 * num_2;
    if (op == "/") {
        if (num_2 == 0) report_Error_zero();
        return num_1 / num_2;
    }
    else{
        report_Error();
    }
}

std::string remove_Invalid_Chars(const std::string& input) {
    std::string validChars = "0123456789.+-*/() ";
    std::string infix;
    std::copy_if(input.begin(), input.end(), std::back_inserter(infix), [&](char ch) { return validChars.find(ch) != std::string::npos; });
    return infix;
}

std::queue<std::string> Infix_To_Postfix(const std::string& infix) {
    
    std::queue<std::string> postfix_Queue;
    std::stack<char> op_Stack;
    std::string tem_Number; 
    bool Number_found   = false; 
    bool Point_found    = false;
    bool Operator_found = false;
    bool Lbracket_found = false;
    bool Rbracket_found = false;
    bool Point_has      = false;
    bool valid_Check    = true;
    int Lbracket_Numbers = 0;
    int Rbracket_Numbers = 0;

    for (char ch : infix) {
        if (isdigit(ch)) {
            tem_Number += ch;
            Number_found   = true;
            Operator_found = false;
            Lbracket_found = false;
        }
        else if (ch == '.') {
            if (!Number_found || Operator_found || Point_found || Point_has) {
                valid_Check = false;
                break;
            }
            tem_Number += ch;
            Point_found  = true;
            Number_found = false;
            Point_has    = true;
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            if (!Number_found || Lbracket_found) {
                valid_Check = false;
                break;
            }
            if (!tem_Number.empty()) {
                postfix_Queue.push(tem_Number);
                tem_Number.clear();
                Number_found = false;
                Point_found  = false;
                Point_has    = false;
            }
            while (!op_Stack.empty() && op_Stack.top() != '(' && Precedence(op_Stack.top()) >= Precedence(ch)) {
                postfix_Queue.push(std::string(1, op_Stack.top()));
                op_Stack.pop();
            }
            op_Stack.push(ch);
            Operator_found = true;
            Point_found    = false;
        }
        else if(ch == '(') {
            if (Number_found || Point_found) {
                valid_Check = false;
                break;
            }
            if (!tem_Number.empty()){
                postfix_Queue.push(tem_Number);
                tem_Number.clear();
                Number_found   = true;
                Operator_found = false;
            }
            op_Stack.push(ch);
            Lbracket_Numbers++;
            Lbracket_found = true;  
        }
        else if (ch == ')') {
            if (Operator_found || !Number_found) {
                valid_Check = false;
                break;
            }
            if (!tem_Number.empty()) {
                postfix_Queue.push(tem_Number);
                tem_Number.clear();
                Number_found = true;
            }
            while (!op_Stack.empty() && op_Stack.top() != '(') {
                postfix_Queue.push(std::string(1, op_Stack.top()));
                op_Stack.pop();
            }
            if (!op_Stack.empty() && op_Stack.top() == '(') {
                op_Stack.pop();
                Rbracket_Numbers++;
            }
        }

    }
        if (Lbracket_Numbers != Rbracket_Numbers || !valid_Check) {
            report_Error();
        }
        if (!tem_Number.empty()) {
            postfix_Queue.push(tem_Number);
        }   
        while (!op_Stack.empty()) {
            postfix_Queue.push(std::string(1, op_Stack.top()));
            op_Stack.pop();
        }
        return postfix_Queue;
}


double calculate_Postfix(const std::queue<string>& postfix) {
    std::stack<double> result_Stack;
    std::queue<string> postfix_Buffer(postfix);
    while (!postfix_Buffer.empty()) {        
        std::string Buffer = postfix_Buffer.front();
        postfix_Buffer.pop();
        if (isdigit(Buffer[0]) || (Buffer[0] == '-' && Buffer.length() > 1)) {
            double num = std::stod(Buffer);
            result_Stack.push(num);
        }
        else {
            if (result_Stack.size() < 2) {
                report_Error();
            }
            double num_2 = result_Stack.top();
            result_Stack.pop();
            double num_1 = result_Stack.top();
            result_Stack.pop();
            result_Stack.push(calculate(num_1, num_2, Buffer));
        }
    }
    if (result_Stack.size() != 1) {
        report_Error();
    }
    return result_Stack.top();
}

int main() {
    std::string input;
    std::getline (std::cin, input);
    std::string infix = remove_Invalid_Chars (input); //Check!  Works!
    std::queue<string> postfix = Infix_To_Postfix (infix);
    double result = calculate_Postfix(postfix);
    cout << result << endl;
    return 0;
}
            \end{lstlisting}
            \end{mdframed}
    
    \subsection{$makefile$}
    The analysis report is an analysis of a $Makefile$ file that compiles and generates an executable file called $test$, 
    and also contains the ability to generate code documentation and reports.
        \subsubsection{Command}
            \begin{itemize}
                \item $make\;all$:\; Perform compilation to generate executables, code documentation, and reports;
                \item $make\;test$:\; Compile $main.cpp$ to generate an executable file named $test$;
                \item $make\;doc$:\; Generate code documentation for $main.cpp$.
                \item $make\;report$:\; Compile $report.tex$ to generate a report file;
                \item $make\;clear$:\; Make it easy to find the target file;
                \item $make\;clean$:\; Clean up generated objects, executables, report files, and related output and temporary files;
            \end{itemize}
        \subsubsection{Codes}
        \begin{mdframed}[linewidth=0.5pt,linecolor=black]
            \begin{lstlisting}[language=make, numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
CPP = g++
CPPRULE = -std=c++11
SRCS = main.cpp
OBJS = $(SRCS:.cpp=.o)
TARGET = test
TEX_FILE = report


all: $(TARGET) doc report

$(TARGET): $(OBJS)
	$(CPP) $(CPPRULE) $(OBJS) -o $(TARGET)

doc: $(SRCS)
	doxygen Doxyfile

$(TEX_FILE): 
	xelatex $(TEX_FILE).tex
	xelatex $(TEX_FILE).tex

clear:
	rm -f report.aux report.log report.toc
 
clean:
	rm -f $(OBJS) $(TARGET)  report.pdf report.aux report.log main.o main doxygen_warnings.log HybridCalculator.tag report.toc
	rm -rf output latex

.PHONY: all clean doc report
            \end{lstlisting}
            \end{mdframed}
            
    \subsection{$run$}
    This script file is mainly used to check the existence and permissions of input files and executable files, 
    pass the input files to the executable file line by line for processing, and store the results in the output file.
        \subsubsection{Codes}
            \begin{mdframed}[linewidth=0.5pt,linecolor=black]
            \begin{lstlisting}[numbers=left, numbersep=2em, basicstyle=\ttfamily, breaklines=true]
#!/bin/bash  
  
# Check input.txt
if [ ! -f "input.txt" ]; then  
  echo "Error: File input.txt may do not exist "  
  exit 1  
fi  
  
# Check test
if [ ! -x "test" ]; then  
  echo "Error: The executable file test may do not exist or does not have execute permissions"  
  exit 1  
fi  
  
# Create output
> output  
  
# Process the input file line by line
while IFS= read -r line || [[ -n "$line" ]]; do
  echo "$line" | ./test >> output #Stores result in output
done < input.txt

echo "The calculation result is saved in the file 'output'. " 
            \end{lstlisting}
            \end{mdframed}
    \subsection{$Doxyfile$}
    The configuration file used to configure the Doxygen tool.
    
    \subsection{$report.tex$}
    Used to generate project report documents.

    \subsection{$input.txt$}
    It is used to test the operation of the project program.

\section{Conclusion}
In general, the code for a four-function arithmetic calculator is implemented using queues and stacks, 
and it includes a comprehensive process for checking erroneous inputs.

\end{document}
